package com.cn.codebrush.二叉树;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Boolean
 * @Date 2022/5/24 10:24
 * @Version 1.0
 */
public class No965单值二叉树 {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(9);
        TreeNode a = new TreeNode(9);
        TreeNode b = new TreeNode(6);
        TreeNode c = new TreeNode(9);
        TreeNode d = new TreeNode(9);
        tree.left = a;
        tree.right = b;
        a.left = c;
        a.right = d;

        System.out.println(isUnivalTree(tree));
    }


    /**
     * 解法二
     * @param root
     * @return
     */
    public static boolean isUnivalTree2(TreeNode root) {
        if(root == null){
            return true;
        }
        if(root.left != null){
            if(root.val != root.left.val || !isUnivalTree(root.left)){
                return false;
            }
        }
        if(root.right != null){
            if(root.val != root.right.val || !isUnivalTree(root.right)){
                return false;
            }
        }
        return true;
    }


    /**
     * 解法一
     */
    static List<Integer> list = new ArrayList<>();
    public static boolean isUnivalTree(TreeNode root) {
         isUnivalTreeHelper(root,root.val);
         for(int i=0;i<list.size();i++){
             if(list.get(i) == 1){
                 return false;
             }
         }
         return true;
    }

    public static void isUnivalTreeHelper(TreeNode root,int val) {
        if(root.val != val){
          list.add(1);
          return;
        }
        if(root.left != null){
            isUnivalTreeHelper(root.left,val);
        }
        if(root.right != null){
            isUnivalTreeHelper(root.right,val);
        }

    }
}
